자료구조데이터를 효과적으로 저장하고, 처리하는 방법에 대한 이해(메모리 성능)
자료구조 개요
자료와 알고리즘효율적인 자료구조 설계를 위해 알고리즘이 필요하고,
효율적인 알고리즘 설계를 위해 자료구조가 필요함
프로그램 성능 측정 방법론시간 복잡도(Time complexity): 연산횟수
공간 복잡도(Space complexity): 사용되는 메모리의 양
시간과 공간은 반비례 관계이다.
시간복잡도를 표현할 때는 최악의 경우를 나타내는 Big-O 표기법을 사용
ex) 1차 반복구문-> O(n), 2차 반복구문 -> O(n^2)
[예시] n이 1000이라면
n: 1,000번의 연산
nlogn: 약 10,000번의 연산
n^2: 1,000,000번의 연산
n^3: 1,000,000,000번의 연산
보통 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요된다.
시간복잡도는 항상 큰항과 계수만 표시
현실적의 다양한 문제에서는 시간제한이 약 1초 정도라고 생각하면 된다.
공간복잡도를 표기할 때는 일반적으로 MB 단위로 표기한다.
int a[1000]; 4KB
int a[1000000]: 4MB
int a[2000][2000]: 16MB